package 剑指offer.第4天;

import java.util.Arrays;

/**
 * 剑指 Offer 53 - II. 0～n-1中缺失的数字
 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
 示例 1:
 输入: [0,1,3]
 输出: 2
 */
//对于有序的数组, 都应该想到用二分法搜索
class Solution3 {
    public int missingNumber4(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        while (start <= end ) {
            int mid = (start + end) / 2;
            if (nums[mid] == mid) start = mid + 1;
            else if (nums[mid] > mid) end = mid - 1;
        }
        return start;
    }
    // 有序数组直接二分
    public int missingNumber3(int[] nums) {
        int left = 0, right = nums.length - 1;
        // 下雨等于
        while(left <= right) {
            // 防溢出的写法，位运算提速，这里注意位运算的优先级问题，需要用括号括起来
            int mid = left + ((right - left) >> 1);
            if(nums[mid] == mid) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }
    //二分法：对于有序的数组, 都应该想到用二分法搜索
    public int missingNumber2(int[] nums) {
        int left = 0, right = nums.length - 1, mid;
        while(left <= right){
            mid = (right + left)>>1;
            if(nums[mid] == mid) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }
    // 1、理论的和减去实际的和即为缺少的数字
    public int missingNumber1(int[] nums) {
        //计算出0-n的和  n*(n+1)/2
        int sum = nums.length * (nums.length+1)/2;
        return  sum - Arrays.stream(nums).sum() ;
    }
    public int missingNumber(int[] nums) {
        int num = 0;
        for (int i = 0; i < nums.length; i++) {
            num = nums[i];
            if (num != i) {
                return i;
            }
        }
        return ++num;
    }

    public static void main(String[] args) {
        int[] nums = {0,1};
        int s1 = new Solution3().missingNumber(nums);
        System.out.println("s1 = " + s1);

    }
}